\label{sect:desarrollo}

\subsection{Aproximaci'on de la trayectoria de los misiles}

Como se indic'o en la secci'on~\ref{sect:teoria}, se usar'an splines para
aproximar la trayectoria de los misiles. Conociendo $m$ puntos de la 
trayectoria $(x_1,y_1),...,(x_m,y_m)$ se puede aproximar cada coordenada
mediante un spline de modo que $x(t)$ ser'a la coordenada $x$ del misil en
tiempo $t$ e $y(t)$ la coordenada $y$.

Como indica el enunciado, utilizaremos para esto splines naturales. A partir
de aqu'i supondremos que queremos desarrollar el spline $x(t)$ que interpola 
los puntos $(t_1=1,x_1),...,(t_m=m,x_m)$. Luego, de modo an'alogo se construye
el spline $y(t)$. Notar que ambos splines solo estar'an definidos de manera
interesante en el intervalo real $[1,m]$.

Definamos $x(t)$ utilizando polinomios c'ubicos por secci'on:
$$x(t) = P_i(t) \mbox{ sii } i \leq t < i+1,$$
donde
$$P_i(t) = a_i x^3 + b_i x^2 + c_i x + d_i \hspace{0.2cm} 
	\forall 1 \leq i \leq m-1.$$

Ahora hace falta definir las constantes $a_i$, $b_i$, $c_i$ y $d_i$ y el 
spline quedar'a definido. Para esto contamos con el siguiente sistema de
ecuaciones:
$$
\begin{array}{rclc}
P_i(i) &=& x_i \hspace{0.2cm} &  \forall 1 \leq i \leq m-1 \\
P_i(i+1) &=& x_{i+1} & \forall 1 \leq i \leq m-1\\
{P_i}'(i+1) &=& {P_{i+1}}'(i+1) & \forall 1 \leq i \leq m-2\\
{P_i}^{(2)}(i+1) &=& {P_{i+1}}^{(2)}(i+1) & \forall 1\leq i\leq m-2\\
{P_1}^{(2)}(1) &=& 0 \\
{P_{m-1}}^{(2)}(m) &=& 0 \\
\end{array}
$$

Que puede reescribirse en t'erminos de las constantes que buscamos de la
siguiente manera:

$$
\begin{array}{rclc}
a_i i^3 + b_i i^2 + c_i i + d_i &=& x_i \hspace{0.2cm} &  \forall 1 \leq i \leq m-1 \\
a_i (i+1)^3 + b_i (i+1)^2 + c_i (i+1) + d_i  &=& x_{i+1} & \forall 1 \leq i \leq m-1\\
3 a_i (i+1)^2 + 2 b_i (i+1) + c_i &=& 3 a_{i+1} (i+1)^2 + 2 b_{i+1} (i+1) + c_{i+1} & \forall 1 \leq i \leq m-2\\
6 a_i (i+1) + 2 b_i &=& 6 a_{i+1} (i+1) + 2 b_{i+1} & \forall 1\leq i\leq m-2\\
6 a_1 + 2 b_1 &=& 0 \\
6 a_{m-1} m + 2 b_{m-1} &=& 0 \\
\end{array}
$$

Notar que el sistema descripto es lineal, tiene $4 (m-1)$ inc'ognitas y 
$2 (m-1) + 2 (m-2) + 2 = 4 (m-1)$ ecuaciones. Por otro lado, puede notarse que
por la forma de la matriz todas sus ecuaciones son LI (para detalles de 
justificaci'on de esto ver las referencias te'oricas sobre splines), por lo 
tanto simplemente aplicando el m'etodo de Gauss se puede 
conseguir el valor de las constantes $a_i$, $b_i$, $c_i$ y $d_i$, con lo cual
se consigue armar el spline completamente.

Observar, por 'ultimo, que cada ecuaci'on del sistema solo afecta constantes
de 2 'indices distintos, por lo cual ordenandolas correctamente se obtiene una
matriz banda que puede ser triangulada mucho m'as eficientemente (ver 
secci'on~\ref{sect:teoria}).

\subsection{Soluci'on propuesta}

En la siguiente secci'on se explicar'a la soluci'on propuesta al problema 
planteado.

El \textit{primer paso} para resolver el problema es el que utiliza lo 
desarrollado en la secci'on anterior sobre splines para calcular la 
trayectoria de los misiles. Esto da como resultado $N$ pares de polinomios 
c'ubicos, a saber uno por cada misil describiendo su trayectoria.

En el \textit{segundo paso} se toma un intervalo de tiempo razonable, dado por 
$m + \epsilon$ y alg'un m'aximo, y se discretiza obteniendo un conjunto de 
valores de $t$. A partir de aqu'i se siguen tres pasos que ser'an analizados 
a continuaci'on:

\begin{enumerate}
\item En primera instancia, por cada valor de $t$, obtenemos $N$ puntos, 
resultantes de la evaluaci'on de los $N$ polinomios obtenidos en el primer 
paso (es decir, se obtiene una aproximaci'on de la posici'on de los misiles 
en esos instantes de tiempo).
Por cada conjunto de $N$ puntos, obtenemos como m'aximo $N \times (N-1)$ 
(esto es dos por cada pareja de misiles) bombas maximales con su respectivo 
conjunto de misiles que elimina. Una bomba es maximal si el conjunto de 
misiles que afecta no es subconjunto de otro conjunto de misiles posibles.
Para todas bomba maximal existe una bomba equivalente (o sea, que mata el 
mismo n'umero de misiles) que tiene al menos dos puntos sobre su perimetro
(ver secci'on~\ref{sect:teoria}),
por lo tanto para cada pareja se generan los a lo sumo dos c'irculos de radio
$r$ que tocan esos dos puntos (puede ser 1 solo c'irculo si los puntos est'an
a exactamente $2r$ de distancia o ninguno si estan mas lejos). Esto genera
como m'aximo $N \times (N-1)$ bombas por cada $t$.

\item Una vez obtenidos todos estos conjuntos, se calcula el 
puntaje de cada tiempo $t$ como la suma de los cuadrados del cardinal de 
conjuntos de misiles eliminados. Calculados estos puntajes, se obtiene un 
ranking y se selecciona la mitad con mayor puntaje.
A continuaci'on se genera un nuevo conjunto de $t$'s del mismo cardinal que 
el anterior utilizando la mitad seleccionada y por cada $t$, se agrega al 
conjunto $t + \delta$ y $t - \delta$, donde $\delta$ se va reduciendo 
dividiendose por 3 en cada iteraci'on.
De esta forma se va mejorando la precisi'on de la discretizaci'on evitando 
la explosi'on exponencial suponiendo que, como las trayectorias son razonables, 
los $t$'s interesantes est'an cerca de otros $t$'s interesantes.
Esto se realiza una cantidad dada de iteraciones (en particular, con 10 es 
suficiente, m'as ya implica demasiada precisi'on y es innecesario).

\item De esta manera se obtiene un conjunto grande de pares con la siguiente 
estructura $<ME, (x, y,t)>$, donde $ME$ es el conjunto de misiles eliminados y 
$(x,y,t)$ representa una bomba en las coordenadas $(x,y)$, en el instante $t$
que elimina ese conjunto de misiles.
Este conjunto es recortado, para que no crezca demasiado, eliminando los 
conjuntos que est'en incluidos en otros. Por ejemplo, si existe una bomba que 
elimina a los misiles 1 y 3, pero tambi'en existe otra bomba que elimina los 
misiles 1, 3 y 4, entonces la primera puede ser descartada por ser superflua.
Luego se hace nuevamente el ranking por puntaje y se seleccionan los primeros.
El puntaje de un conjunto para recortar es $\sum_{i} \alpha+(1/c_{i})$ para 
cada elemento $i$ que contiene. El n'umero $c_{i}$ es la cantidad de veces que
aparece el elemento $i$ entre todos los conjuntos.
El objetivo de esto es otorgarle prioridad a los conjuntos grandes y tambi'en 
a los que contienen elementos poco populares (esto se logra mediante el 
$\alpha$ que es quien decide a cu'al de estas dos cosas se le otorga m'as prioridad).

En el \textit{tercer paso} se agrega una bomba por cada misil que no est'a siendo 
alcanzado por ninguna bomba, por ejemplo si hay alg'un misil aislado muy lejos 
del resto. Si sobran bombas, conviene usar una para matar a ese solo al menos.
Notar que inicialmente, solo se colocan bombas que afectan al menos a dos 
misiles.

En el \textit{cuarto paso} se tiene la bolsa de $<ME, (x, y,t)>$ de cada bomba 
y se desea obtener $K$ (el n'umero de bombas) tal que la uni'on de los
conjuntos representados por la primer coordenada de los $K$ pares sea lo
m'as grande posible.

Para esto se define $F$ como la funci'on que dada una bolsa y un $K$ dice una cantidad 
de conjuntos \textit{interesantes} que se pueden lograr con $K$ bombas.
\begin{center}
	$F(1) = $ conjunto original.\\
	$F(2N) = $ tomar $F(N)$ y probar todos contra todos uniendo los conjuntos resultado.\\
	$F(2N+1) = $ tomar $F(2N)$ y probar todos contra $F(1)$ uniendo los conjuntos resultado
\end{center}

La cantidad de llamados a $F$ es del orden de $\log K$ y 
que en cada llamado se tienen $(cantidad elementos del conjunto^{2})$ cosas 
para probar.

Finalmente, un llamado a $F(K)$ permite quedarse con el mejor conjunto.

En cada llamado de $F$ se recorta el conjunto resultado para no se pase
del l'imite de la misma forma que antes (primero eliminar los
superfluos y luego rankear por $\sum_{i} \alpha+(1/c_{i})$ y seleccionar el
ma's grande), con la diferencia de que en este caso se utiliza un s'olo 
$\alpha$ que se hace grande para $K$'s m'as grandes (a medida que el resultado 
final se encuentra m'as cerca, el tama'no del conjunto cobra mayor importancia
y disminuye el criterio de la popularidad, que s'i es importante a largo plazo).

\end{enumerate}

\subsection{Setting General de la experimentaci'on}
\label{sect:setting}

Para el testing de la soluci'on desarrollada se desarrollo un programa en Python
que toma los siguientes parametros:

\begin{itemize}
 \item $cant\_mediciones$: Es la cantidad de medici'ones que se tendr'a de cada misil
 \item $cant\_misiles$: La cantidad de misiles que se tendr'a en el archivo de salida
 \item $radio\_planeta$: El radio del planeta
 \item $cant\_bombas$: La cantidad de bombas
 \item $radio\_explosion$: El radio de explosi'on de cada bomba
 \item $archivo\_salida$: El nombre del archivo de salida
\end{itemize}

Para generar la trayectoria de cada misil se sigue el siguiente algoritmo:

\begin{itemize}
 \item Para cada misil se elije un punto aleatorio de partida, y un punto aleatorio de impacto dentro del planeta. 
 \item Luego se construye la recta $R$ que pasa por estos puntos.
 \item Se elije como momento de impacto $2\times cant\_mediciones$ y se elije el grado del polinomio que describir'a la trayectoria del misil (para cada coordenada) como un n'umero aleatorio entre 2 y 5. Se elije 5 como grado m'aximo porque un polinomio de grado mucho mayor no ser'ia facilmente aproximable por un Spline. 
 \item Si el grado es 2, el polinomio es la recta que ya se tiene construida. Si el grado es mayor que 2, se elijen $grado - 2$ momentos adicionales.
 \item Para cada momento adicional, se calcula el punto correspondiente en la recta $R$ y se le suma un desplazamiento aleatorio (que depende del cuadrante en el que se est'a, de la distancia que hay entre las posiciones iniciales y finales, y del grado del polinomio que se quiere construir)
 \item Por 'ultimo se devuelve el polinomio interpolador de $Lagrange$ de grado m'inimo que interpola los puntos calculados en el paso anterior para las coordenadas $x$ e $y$
\end{itemize}

Mediante un par de corridas con los ejemplos propuestos por la c'atedra y los
generados se determinaron los par'ametros arbitarios teniendo en cuenta que la
corrida no tarde demasiado y que la efectividad de la misma sea buena. Dichas
corridas no se presentan expl'icitamente puesto que el proceso de 
experimentaci'on no fue sistem'atico sino que la b'usqueda de los par'ametros
se hizo ``probando''.

Se pens'o inicialmente en hacer una red neuronal para llegar al valor 'optimo
de los par'ametros, pero como no estaba dentro del scope principal del TP y ya
hab'ia mucho trabajo en otras cosas, se decidi'o que no val'ia la pena.
